package com.ShangGuiGu.sortAlgorithm.归并排序;

/**
 * 归并排序
 * 将一组数据分为两组数据，分别将两组数据进行排序交换之后
 * 再对两组数据的对应下标进行比较，哪一个小就放在一个新数组中，然后将哪一组的数据下标+1
 * 依次进行，如果其中一组数据到了尽头，也就是下标已经达到最后一个了，没有数据可以往新数组中加入之后
 * 我们直接将还有数据的那一组直接加入到新数组中即可
 * <p>
 * 4 5 7 8                  1 2 3 6
 * |                        |
 * 两个斜杠就是对应比较的数据下标，根据上面的逻辑即可完成归并排序
 */
public class 归并排序 {
    public static void main(String[] args) {
        int[] arr = {4, 5, 7, 8, 1, 2, 3, 6};
        int[] temp2 = {};
        merge(arr, 0, 3, 7, temp2);
        for (int i : temp2) {
            System.out.println(i);
        }
    }

    /**
     * //合并
     *
     * @param arr   需要排序的初始数组
     * @param left  左边数据的索引
     * @param mid   中间的索引
     * @param right 右边数据的索引
     * @param temp  中转数组
     */
    static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;//左边
        int j = mid + 1;//右边
        int t = 0;//中转数组的开始下标，每存一个数据，t+=1;

        while (i <= mid && j <= right) {
            //如果左边大于右边，将左边的值放入temp中并且下标后移
            if (arr[i] < arr[j]) {
                temp[t] = arr[i];
                i = i + 1;
                t = t + 1;
            } else if (arr[j] < arr[i]) {
                //如果右边大于左边，把右边的值加入temp中，然后下标后移
                temp[t] = arr[j];
                t += 1;
                j += 1;
            }
        }

        //到这里就说明有一边的数据放完了，我们现在需要将另一组数据给放到temp中
        while (i <= mid) {
            temp[t] = arr[i];
            t += 1;
            i += 1;
        }
        while (i <= right) {
            temp[t] = arr[j];
            t += 1;
            j += 1;
        }

        //将temp的数组拷贝到arr


    }

    //排序比较
    static void sort(int[] arr) {

    }

}
